Persistent Homology of Coarse-Grained State Space Networks

class: top, left, inverse, title-slide

.title[
# Persistent Homology of Coarse-Grained State Space Networks
]
.author[
### Max Chumley — Mechanical Engineering — Michigan State University —
]
.date[
### 2023-10-05
]

---

background-image: url("data:image/png;base64,#../../people/people.png")
background-size: 800px
background-position: 95% 50%

# Acknowledgements 
.left-column[
<div style="height: 25px;"></div>
&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;

<img src="data:image/png;base64,#../../logos/AFRL.png" width="500" style="display: block; margin: auto;" />
This material is based upon work supported by the Air Force Office of Scientific Research under award number FA9550- 30 22-1-0007

&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;
]

---

# Pipeline

![:img 90%, left, top, 5%, 30%](data:image/png;base64,#../Figs/pipeline/pipeline1.png)

![:img 90%, left, top, 5%, 30%](data:image/png;base64,#../Figs/pipeline/pipeline2.png)
--

![:img 90%, left, top, 5%, 30%](data:image/png;base64,#../Figs/pipeline/pipeline3.png)
--

![:img 90%, left, top, 5%, 30%](data:image/png;base64,#../Figs/pipeline/pipeline4.png)
--

![:img 90%, left, top, 5%, 30%](data:image/png;base64,#../Figs/pipeline/pipeline5.png)

--
![:img 25%, left, top, 5%, 30%](data:image/png;base64,#../Figs/periodic_vid.mp4)
--

![:img 25%, left, top, 5%, 30%](data:image/png;base64,#../Figs/chaotic_vid.mp4)

---

# Motivation - Ordinal Partition Networks (OPN)

---

# Motivation - OPN Lorenz System

- Lorenz System:

`$\frac{dx}{dt}  = \sigma (y-x), \\ \frac{dy}{dt}  = x(\rho-z), \\ \frac{dz}{dt}  = xy-\beta z$`
- Timeseries: `$x(t)$`

- Periodic: `$\sigma=10.0,~\beta=\frac{8}{3},~\rho=100$`
<img src="../Figs/lorenz_1.png"
 width="40%" 
 style="position:absolute; left:55%; top:25%;">

- Chaotic: `$\sigma=10.0,~\beta=\frac{8}{3},~\rho=105$`
<img src="../Figs/lorenz_2.png"
 width="40%" 
 style="position:absolute; left:55%; top:25%;">

---

# Motivation - OPN with Noise 
- Periodic Rossler System

`$\frac{dx}{dt}  = -y -z, \\ \frac{dy}{dt}  = x + ay, \\ \frac{dz}{dt}  = b + z(x-c)$`

- `$a=0.1,~b=0.2,~c=14$`

- Timeseries: `$z(t)$`
--

<img src="../Figs/rossler_1.png"
 width="50%" 
 style="position:absolute; right:5%; top:25%;">
--

---
# Motivation - Undesired Transitions

---

# Coarse-grained State Space Networks (CGSSN)
<img src="../Figs/CGSSN_2d_example_cycle.gif"
 width="90%" 
 style="position:absolute; left:5%; top:30%;">

# Network Formulation

--
<img src="../Figs/network/network_2.png"
 width="80%" 
 style="position:absolute; left:10%; top:20%;">

--
<img src="../Figs/network/network_3.png"
 width="80%" 
 style="position:absolute; left:10%; top:20%;">

--
<img src="../Figs/network/network_4.png"
 width="80%" 
 style="position:absolute; left:10%; top:20%;">

--
<img src="../Figs/network/network_5.png"
 width="80%" 
 style="position:absolute; left:10%; top:20%;">

--
<img src="../Figs/network/network_6.png"
 width="80%" 
 style="position:absolute; left:10%; top:20%;">

--
<img src="../Figs/network/network_7.png"
 width="80%" 
 style="position:absolute; left:10%; top:20%;">

--
<img src="../Figs/network/network_8.png"
 width="80%" 
 style="position:absolute; left:10%; top:20%;">

---

# CGSSN with Noise 
- Periodic Rossler System

`$\frac{dx}{dt}  = -y -z, \\ \frac{dy}{dt}  = x + ay, \\ \frac{dz}{dt}  = b + z(x-c)$`

- `$a=0.1$`
- `$b=0.2$`
- `$c=14$`

- Timeseries: `$z(t)$`
--
<img src="../Figs/rossler_5.png"
 width="65%" 
 style="position:absolute; right:2%; top:20%;">
--
<img src="../Figs/rossler_6.png"
 width="65%" 
 style="position:absolute; right:2%; top:20%;">

---

# Distance Matrix

---

# Graph Dissimilarity Measures - Shortest Path

- Shortest Path: `$C(P)=\sum_{e\in P}w(e)$`

`$$D(a,b)=\min_{P}C(P)$$`

- Unweighted: `$w(e)=1~\forall~e\in P$`

<img src="../Figs/dissimilarity/sp_1.png"
 width="42%" 
 style="position:absolute; left:27%; bottom:2%;">
--

---
# Graph Dissimilarity Measures - Weighted Shortest Path
- Weighted Shortest Path: `$C'(P)=\sum_{e\in P}\frac{1}{w(e)}$`

`$$D(a,b)=\sum_{e\in P}w(e)$$`

- Shortest Weighted Path: `$D(a,b)=|\min_P C'(P)|$`
--
<img src="../Figs/dissimilarity/wsp_1.png"
 width="60%" 
 style="position:absolute; left:20%; bottom:5%;">
--
<img src="../Figs/dissimilarity/wsp_2.png"
 width="60%" 
 style="position:absolute; left:20%; bottom:5%;">
--
<img src="../Figs/dissimilarity/wsp_3.png"
 width="60%" 
 style="position:absolute; left:20%; bottom:5%;">
--
<img src="../Figs/dissimilarity/wsp_4.png"
 width="60%" 
 style="position:absolute; left:20%; bottom:5%;">

<!-----------------
 Script: 
 In order to compute persistence on an object, we need to know the distances between points in the object. This is done by computing a distance matrix for the network. First we need to define how distances are computed on the network. We have 4 methods for doing this and the first is shown here. This method is called the shortest path distance where we minimize the cost function c(p) as the sum of the weights. so we are looking for the path in the network with minimal weights.
 
 If the network is unweighted we set all w(e) to be 1 and the shortest path becomes the path with the fewest edges.

The second distance is called the weighted shortest path. Here the cost function is now the sum of reciprocal weights and we take the distance as the sum of the weights along the path that minimizes the cost. Including weight information in the distance encodes information about the frequency of traversal of a path.

The third distance is called the shortest weighted path. This is similar to the weighted shortest path but we take the distance to be the number of edges in the path that minimized the cost function instead of the sum of the weights. This method gives priority to well traveled paths.
 
----------------->

---

# Graph Dissimilarity Measures - Diffusion Distance

- Diffusion Distance: `$P(i,j)=\frac{A(i,j)}{\sum_{k=1}^{|V|}A(i,k)}$`

- `$A$`: Adjacency matrix with no self loops
  - `$P$`: Probability of transitioning from `$i$` to `$j$`

- `$t$`-random walk: `$P^t(a,b)$`

- Lazy Transition Probability: `$\widetilde{\mathbf{P}} = \frac{1}{2}\left[\mathbf{P}(a, b) + \mathbf{I}\right]$`

`$$d_t(a,b) = \sqrt{ \sum_{c \in V}  \frac{1}{\mathbf{d}(c)} { \left[ \widetilde{\mathbf{P}}^t (a,c) - \widetilde{\mathbf{P}}^t (b,c) \right] }^2 }$$`

--
<img src="../Figs/clear_slide.png"
 width="80%" 
 style="position:absolute; left:5%; top:15%;">
<img src="../Figs/dissimilarity/diff_1.png"
 width="80%" 
 style="position:absolute; right:10%; top:25%;">

--
<img src="../Figs/dissimilarity/diff_2.png"
 width="80%" 
 style="position:absolute; right:10%; top:25%;">

--
<img src="../Figs/dissimilarity/diff_3.png"
 width="80%" 
 style="position:absolute; right:10%; top:25%;">

--
<img src="../Figs/dissimilarity/diff_4.png"
 width="80%" 
 style="position:absolute; right:10%; top:25%;">

--
<img src="../Figs/dissimilarity/diff_5.png"
 width="80%" 
 style="position:absolute; right:10%; top:25%;">

<!-----------------
 Script:

The final method is called the diffusion distance where we study the probability of transitioning between nodes. We also account for the lazy transition probability where a walk may remain at the current vertex.
 
----------------->

---

# Persistent Homology

---

# Persistence of Networks
<img src="../Figs/pd/pd_0.png"
 width="70%" 
 style="position:absolute; left:15%; top:20%;">

--
<img src="../Figs/pd/pd_1.png"
 width="70%" 
 style="position:absolute; left:15%; top:20%;">
<img src="../Figs/pd/swp_eqn.png"
 width="40%" 
 style="position:absolute; right:5%; top:5%;">
--
<img src="../Figs/pd/pd_2.png"
 width="70%" 
 style="position:absolute; left:15%; top:20%;">

--
<img src="../Figs/pd/pd_3.png"
 width="70%" 
 style="position:absolute; left:15%; top:20%;">

--
<img src="../Figs/pd/pd_4.png"
 width="70%" 
 style="position:absolute; left:15%; top:20%;">

--
<img src="../Figs/pd/pd_5.png"
 width="70%" 
 style="position:absolute; left:15%; top:20%;">

--
<img src="../Figs/pd/pd_6.png"
 width="70%" 
 style="position:absolute; left:15%; top:20%;">

--
<img src="../Figs/pd/pd_7.png"
 width="70%" 
 style="position:absolute; left:15%; top:20%;">

---

# Simple Example
<img src="../Figs/pd_example.png"
 width="70%" 
 style="position:absolute; left:15%; top:20%;">

---

# State Identification

---
# Empirical Testing of 23 Dynamical Systems

--
<img src="../Figs/procedure_2.png"
 width="80%" 
 style="position:absolute; left:10%; bottom:5%;">

--
<img src="../Figs/procedure_3.png"
 width="80%" 
 style="position:absolute; left:10%; bottom:5%;">

--
<img src="../Figs/procedure_4.png"
 width="80%" 
 style="position:absolute; left:10%; bottom:5%;">

--
<img src="../Figs/mds_2.png"
 width="54%" 
 style="position:absolute; right:23%; top:20%;">

---

# Dynamic State Identification Results

---

# Thank you! 
# Any questions?

<img src="../Figs/teaspoon.png"
 width="55%" 
 style="position:absolute; right:5%; top:5%;">

Myers, A. D., **Chumley, M. M.**, Khasawneh, F. A., & Munch, E. (2023). Persistent homology of coarse-grained state-space networks. Physical Review E, 107(3), 034303.

---

# Experimental Results - Periodic

---

# Experimental Results - Chaotic